package org.algorithm.YaYa.数组.三月.第三周;

/**
 * @date 2022-03-18 星期五17:33
 *
 * url:  https://leetcode-cn.com/problems/best-sightseeing-pair/
 */
public class 最佳观光组合 {

    public static void main(String[] args) {
        int[] nums = {8,1,5,2,6};
        System.out.println(maxScoreSightseeingPair(nums));
    }

    /**
     *
     * 输入：values = [8,1,5,2,6]
     * 输出：11
     * 解释：i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11
     *
     */
    public static int maxScoreSightseeingPair(int[] values) {
        int ans = 0, mx = values[0] + 0;
        for (int j = 1; j < values.length; ++j) {
            ans = Math.max(ans, mx + values[j] - j);
            // 边遍历边维护
            mx = Math.max(mx, values[j] + j);
        }
        return ans;
    }

}
